package com.origin.niuke.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * NC115 栈和排序
 * 算法：栈 + 动态规划
 * 定义 dp[i], 表示 [i, n - 1] 中最大的数
 * 当 a[i] == dp[i] 时, 表示 a[i] 是 [i, n - 1] 的最大数, 直接放入 ans 中
 * 再判断栈顶的元素是否 ≥ dp[i + 1]
 *
 * @author yezh
 * @date 2022/11/15 22:04
 */
public class NC115 {

    public int[] solve (int[] a) {
        // write code here
        int n = a.length;
        // 表示 [i, n - 1] 的最大数
        int[] dp = new int[n + 1];
        dp[n] = dp[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) dp[i] = a[i] > dp[i + 1] ? a[i] : dp[i + 1];
        Deque<Integer> deque = new ArrayDeque<>(n);
        int[] ans = new int[n];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == dp[i]) {
                ans[idx++] = a[i];
                while (!deque.isEmpty() && deque.peek() >= dp[i + 1]) ans[idx++] = deque.poll();
            } else deque.push(a[i]);
        }
        while (!deque.isEmpty()) ans[idx++] = deque.poll();
        return ans;
    }

}
